package com.xk._02算法篇._01sort.sort.cmp;

import com.xk._02算法篇._01sort.sort.Sort;
import com.xk.tools.Integers;

/**
 * @description: 快速排序
 * @author: xu
 * @date: 2022/10/2 10:43
 */
public class QuickSort<E extends Comparable<E>> extends Sort<E> {
    /**
     * 快速排序
     */
    private void quickSort(){
        quickSort(0, array.length);
    }

    /**
     * 对 [begin, end) 范围的元素进行快速排序
     * 最好的情况：左右均匀
     *      T(n) = T(n/2) + T(n/2) + O(n)
     *      T(n) = 2 * T(n/2) + O(n) = O(nlogn)
     * 最坏的情况：轴点一直在最右边或者最最左边
     *      T(n) = T(n-1) + O(n) = O(n^2)
     * @param begin
     * @param end
     */
    private void quickSort(int begin, int end){
        if (end - begin < 2) return;
        // 确定轴点位置 O(n)
        int mid = pivotIndex(begin, end); // O(n)
        // 对子序列进行快速排序
        quickSort(begin, mid);
        quickSort(mid+1, end);
    }

    /**
     * 构造出 [begin, end) 范围的轴点元素
     * @param begin
     * @param end
     * @return 轴点元素的最终位置
     */
    private int pivotIndex (int begin, int end) {
        // 随机选择一个元素跟 begin 位置进行交换
        swap(begin, begin + (int) (Math.random() * (end - begin)));

        // 备份begin位置的元素
        E pivot = array[begin];
        // end指向最后一个元素
        end--;
        while (begin < end) {
            while (begin < end) {
                if (cmp(pivot, array[end]) < 0) { // 右边元素 > 轴点元素
                    end--;
                } else { // 右边元素 <= 轴点元素
                    array[begin++] = array[end];
                    break;
                }
            }
            while (begin < end) {
                if (cmp(pivot, array[begin]) > 0) {// 左边元素 < 轴点元素
                    begin++;
                } else { // 左边元素 >= 轴点元素
                    array[end--] = array[begin];
                    break;
                }
            }
        }
        //将轴点元素放入最终的位置
        array[begin] = pivot;
        // 返回轴点元素的位置
        return begin;
    }

    @Override
    protected void sort() {
        quickSort();
    }

    public static void main(String[] args) {
        Integer[] array = Integers.random(20, 1, 100);
        Integers.println(array);

        Sort<Integer> quickSort = new QuickSort<>();
        quickSort.sort(array);
        Integers.println(array);
        System.out.println(quickSort);
    }
}
